//
// Created by Criinal Nicole on 2021/5/10.
//

#ifndef GFD_GFDDISCOVERING_H
#define GFD_GFDDISCOVERING_H


#include <utility>
#include <queue>
#include <fstream>

#include "../dataStructure/Graph.h"
#include "../dataStructure/GFD.h"
#include "VF2.h"
#include "SubGraphMatch.h"

class GFDDiscovering {
public:
    const int MAX_PATTERN_NUM = 200000;
    int cntPattern{0};

    Graph dataGraph;

    explicit GFDDiscovering(Graph &data) :
            dataGraph(data) {}

    std::set<int> vertexLabelSet;

    std::set<EdgeModel> edgeLabelSet;

//    std::map<std::pair<label, PropertyName>, std::set<PropertyValue>>
    std::map<std::pair<int, int>,
            std::set<PropertyValue>> propertySet;

    void patternGrow(std::set<int> &suppList, int suppValue, std::string fileName);

    void addEdge(Graph &pattern, std::vector<Graph> &retGraphVector);

    void addEdgeNewVertex(Graph &pattern, std::vector<Graph> &retGraphVector);

    void addEdge(Vertex &from, Vertex &to,
                 Graph &pattern,
                 std::vector<Graph> &retGraphVector);

    static bool isDiscovered(std::vector<Graph> &discoveredPattern, Graph &gfdPattern);

    static bool isSubgraph(Graph &pattern, Graph &dataGraph);

    static bool isIsomorphism(Graph &lft, Graph &rht);
};

bool GFDDiscovering::isSubgraph(Graph &pattern, Graph &dataGraph) {
    if (pattern.size() > dataGraph.size())return false;
    VF2 vf2(pattern, dataGraph);
    bool isMatched = false;

    const auto matchFunction = [&](
            std::map<int, int> &matchState,
            bool &isMatched) {
        if (!isMatched) {
            isMatched = true;
        }
        return false;
    };

    vf2.vf2Engine(
            [&](std::map<int, int> &matchState) {
                return matchFunction(matchState, isMatched);
            },
            defaultPruneCheck);

    return isMatched;
}

bool GFDDiscovering::isIsomorphism(Graph &lft, Graph &rht) {
    if (!isSubgraph(lft, rht))return false;
    return isSubgraph(rht, lft);
}

bool GFDDiscovering::isDiscovered(std::vector<Graph> &discoveredPattern, Graph &gfdPattern) {
    for (auto &pattern:discoveredPattern) {
        if (isIsomorphism(pattern, gfdPattern))return true;
    }
    return false;
}

void GFDDiscovering::patternGrow(std::set<int> &suppList, int suppValue, std::string fileName) {
//    更新信息
    dataGraph.updateVertexLabelInfo(vertexLabelSet);
    dataGraph.updateEdgeLabelInfo(edgeLabelSet);
    dataGraph.updatePropertySetInfo(propertySet);

    cntPattern = 0;

    GFD initGFD;
    std::vector<Graph> discoveredPattern{};
    std::queue<GFD> gfdQueue;

    std::ofstream oFStream(fileName);
    if (!oFStream.is_open()) {
        std::cout << "can't create file:"
                  << fileName << std::endl;
        return;
    }
//    采用BFS的方法进行拓展
    initGFD.init();
    gfdQueue.push(initGFD);
    while (!gfdQueue.empty()) {
        auto tmpGFD = gfdQueue.front();
        gfdQueue.pop();
//        如果该图已经找到过 则不继续匹配
//        后续可重写该方法
        if (isDiscovered(discoveredPattern, tmpGFD._pattern)) {
            continue;
        }

        discoveredPattern.push_back(tmpGFD._pattern);
//        std::cout << "discoveredPattern: ";
//        for (auto &i:discoveredPattern) {
//            std::cout << i << ", ";
//        }
//        std::cout << "\n";
        if (!tmpGFD._pattern.empty()) {
            std::cout << tmpGFD << std::endl;
            tmpGFD.fileOut(oFStream);
        }

        std::vector<Graph> retGraphVector;
        if (tmpGFD._pattern.countEdge() < GFD::_maxEdgeSize)
            addEdge(tmpGFD._pattern, retGraphVector);
        if (tmpGFD._pattern.size() < GFD::_maxVertexSize)
            addEdgeNewVertex(tmpGFD._pattern, retGraphVector);
        if (cntPattern >= MAX_PATTERN_NUM)continue;

//        对于生成的新pattern 生成新的literal
        for (auto &pattern: retGraphVector) {
            GFD addEdgeGFD(pattern, tmpGFD._literalPairVector);
            if (pattern.size() > tmpGFD._pattern.size()) {
                addEdgeGFD.addLiteralDFS(propertySet);
            }

            //std::cout << addEdgeGFD << std::endl;

            int cntSupp = 0;

//            计算其支持度
            std::vector<std::pair<int, bool>> tmpLIndexVector;
            auto tmpLiteralBase = addEdgeGFD._literalPairVector;

            for (int i = 0; i < addEdgeGFD._literalPairVector.size(); ++i) {
                auto &literalPair = addEdgeGFD._literalPairVector.at(i);
                cntSupp = 0;
                suppMatch(addEdgeGFD._pattern, dataGraph, suppList,
                          suppValue, cntSupp,
                          [&](std::map<int, int> &matchState) {
                              return GFD::literalCheck(addEdgeGFD._pattern, dataGraph, matchState, literalPair);
                          });
//                std::cout << "supp: " << cntSupp << " " << "SUPP: " << suppValue << std::endl;
//                if (cntSupp < suppValue) {
//                    addEdgeGFD._literalPairVector.erase(addEdgeGFD._literalPairVector.begin() + i);
//                }
                tmpLIndexVector.emplace_back(i, cntSupp >= suppValue);
            }

            std::stable_partition(tmpLIndexVector.begin(), tmpLIndexVector.end(),
                                  [](std::pair<int, bool> pair) {
                                      return pair.second;
                                  });
            addEdgeGFD._literalPairVector.clear();

            for (auto &tmpPair: tmpLIndexVector) {
                if (!tmpPair.second)break;
                addEdgeGFD._literalPairVector.push_back(tmpLiteralBase[tmpPair.first]);
            }
            if (addEdgeGFD._literalPairVector.empty())continue;

            gfdQueue.push(addEdgeGFD);

        }

    }
}

void GFDDiscovering::addEdge(Vertex &from, Vertex &to,
                             Graph &pattern,
                             std::vector<Graph> &retGraphVector) {
    for (auto &labelEdge:edgeLabelSet) {
        if (from.getLabel() == labelEdge.getFromVertex()
            && to.getLabel() == labelEdge.getToVertex()) {
            auto tmpPattern = pattern;
            Graph::makeEdge(tmpPattern[from.getId()],
                            tmpPattern[to.getId()],
                            labelEdge.getLabel());
            if (tmpPattern.size() <= GFD::_maxVertexSize ||
                !isDiscovered(retGraphVector, tmpPattern)) {
                retGraphVector.push_back(tmpPattern);
                if (++cntPattern >= MAX_PATTERN_NUM)return;
            }
        }
    }
}

void GFDDiscovering::addEdge(Graph &pattern,
                             std::vector<Graph> &retGraphVector) {
    for (auto &from :pattern) {
        for (auto &to :pattern) {
            if (from.getId() == to.getId())continue;
            addEdge(from, to, pattern, retGraphVector);
        }
    }
}

void GFDDiscovering::addEdgeNewVertex(Graph &pattern,
                                      std::vector<Graph> &retGraphVector) {

//    枚举出边
    for (auto &vertexLabel :vertexLabelSet) {
        auto tmpPattern = pattern;
        tmpPattern.emplace_back(pattern.size(), vertexLabel);
        auto &from = tmpPattern[pattern.size()];
        if (pattern.empty()) {
            retGraphVector.push_back(tmpPattern);
            continue;
        } else {
            for (auto &to:pattern) {
                addEdge(from, to, tmpPattern, retGraphVector);
                if (++cntPattern >= MAX_PATTERN_NUM)return;
            }
        }
    }
//    枚举入边
    for (auto &vertexLabel :vertexLabelSet) {
        auto tmpPattern = pattern;
        tmpPattern.emplace_back(pattern.size(), vertexLabel);
        auto &to = tmpPattern[pattern.size()];
        for (auto &from:pattern) {
            addEdge(from, to, tmpPattern, retGraphVector);
            if (++cntPattern >= MAX_PATTERN_NUM)return;
        }
    }
}


#endif //GFD_GFDDISCOVERING_H
